//
//  InsertMethodVC.m
//  test02
//
//  Created by lzh on 2021/4/19.
//  Copyright © 2021 NO. All rights reserved.
//

#import "InsertMethodVC.h"

@interface InsertMethodVC ()

@end

@implementation InsertMethodVC

- (void)viewDidLoad {
    [super viewDidLoad];
    self.view.backgroundColor= [UIColor whiteColor];
}
// 插入排序 ： 两个for循环 第一个for 挨个取数组元素（7） 第二for 用取出来的元素根他前面位置（10，3）的元素比较 找到合适的位置插入
-(void)method1{
    NSArray * array = @[@(10),@(3),@(7),@(1),@(8)];
    NSMutableArray * arr = [NSMutableArray arrayWithArray:array];
    for (int i=0; i<array.count; i++) {
        for (int j=i; j>0; j--) {
//        if (i+1==arr.count) {
//            break;
//        }
        if ([arr[j] intValue]>[arr[j-1] intValue]) {
                id temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }
        }
        
    }
    
    NSLog(@"%@",arr);
}
//折半插入排序 （一直取中间的坐标 判断从左边找 右面找 继续取中间坐标 直到low 跟 high相邻）
-(void)method2{
    
    NSArray * array1 = @[@(10),@(3),@(7),@(1),@(8)];
    NSArray * array2 = @[@(1),@(2),@(8),@(10),@(12)];

    NSMutableArray * arr1 = [NSMutableArray arrayWithArray:array1];
    NSMutableArray * arr2 = [NSMutableArray arrayWithArray:array2];
    int temp =7;
//    for (int i=0; i<arr2.count; i++) {
        int low = 0;
        int high = arr2.count - 1;
        while (low<high-1) {
            int mid = (low+high)/2;
            if (temp>[arr2[mid]intValue]) {
                low = mid;
            }else{
                high = mid;
            }
        }
//    }
    [arr2 insertObject:@(temp) atIndex:low+1];
    
    NSLog(@"%@",arr2);
    
}
-(void)touchesBegan:(NSSet<UITouch *> *)touches withEvent:(UIEvent *)event{
    
    [self method2];
}

@end
